package com.链表;

/**
 * 给出一个单词列表，其中每个单词都由小写英文字母组成。
 *
 * 如果我们可以在 word1 的任何地方添加一个字母使其变成 word2，那么我们认为 word1 是 word2 的前身。例如，"abc" 是 "abac" 的前身。
 *
 * 词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此类推。
 *
 * 从给定单词列表 words 中选择单词组成词链，返回词链的最长可能长度。
 *  
 *
 * 示例：
 *
 * 输入：["a","b","ba","bca","bda","bdca"]
 * 输出：4
 * 解释：最长单词链之一为 "a","ba","bda","bdca"。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-string-chain
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 最长字符串链 {
    static class Solution {
        public int longestStrChain(String[] words) {
            int max = 1;
            boolean flag = true;
            for(int i = 0,j=1;j<words.length-1;i++,j++){

                String[] temp = words[i].split("");
                for(String s:temp){
                    if(!words[j].contains(s)){
                        flag = false;
                        break;
                    }
                    else{
                        flag = true;
                    }
                }
                if(flag){
                    ++max ;
                }
                else{
                    words[j]  = words[i];
                }
            }
            return max==1 ? max : ++max;
        }
    }

    public static void main(String[] args) {

        Solution solution = new Solution();
        solution.longestStrChain(new String[]{"a","b","ba","bca","bda","bdca"});


    }
}
